package org.flint.data.structure.leetcode;

/**
 * @author flint92
 */
public class RemoveLinkedListElements {

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     *
     * Remove all elements from a linked list of integers that have value val.
     *
     * Example:
     *
     * Input:  1->2->6->3->4->5->6, val = 6
     * Output: 1->2->3->4->5
     *
     * @return      new list
     */
    public ListNode removeElements(ListNode head, int val) {

        if (head == null) {
            return null;
        }

//        while (head != null && head.val == val) {
//            ListNode del = head;
//            head = head.next;
//            del.next = null;
//        }
//
//        if (head == null) {
//            return null;
//        }
//
//        ListNode pre = head;
//        while (pre.next != null) {
//            if (pre.next.val == val) {
//                ListNode del = pre.next;
//                pre.next = del.next;
//                del.next = null;
//            } else {
//                pre = pre.next;
//            }
//        }
//        return head;
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = head;
        ListNode pre = dummyHead;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                cur.next = null;
                cur = pre.next;
            } else {
                pre = pre.next;
                cur = cur.next;
            }

        }
        return dummyHead.next;
    }


    public ListNode removeElementsRecurse(ListNode head, int val) {
        if (head == null) {
            return null;
        }

        head.next = removeElementsRecurse(head.next, val);
        return head.val == val ? head.next : head;
    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

}
